<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    //  给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

    // 子数组 是数组中的一个连续部分。

    // 示例1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    // 输出：6
    // 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
    // 示例2：输入：nums = [5,4,-1,7,8]
    // 输出：23

    // function maxSubArray(nums) {
    //   let minSum = 0;
    //   let maxSum = -Infinity;  // 数组最大和可能是正数也可能是负数
    //   for (let i = 0; i < nums.length; i++) {
    //     minSum += nums[i];
    //     // Math.max() 函数返回作为输入参数的最大数字，如果没有参数，则返回 -Infinity。
    //     maxSum = Math.max(maxSum, minSum);
    //     minSum = Math.max(minSum, 0);
    //   }
    //   return maxSum;
    // };
    // maxSubArray([4,6,8,-8,5,-3,9,7,-2])
    // console.log(maxSubArray([4,6,8,-8,5,-3,9,7,-2]));
     
    
    // 动态规划
    // f(i) 代表的第i个元素结尾的连续子数组的最大和
    //  max{ f(i) }
    // f(i) = max{ f(i-1) + nums[i], nums[i]}
    function maxSubArray(nums) {
      let pre = 0
      let max = num[0]
      for ( let i = 1; i <nums.length; i++) {
      pre = Math.max(pre + nums[i]), nums[i]
      max = Math.max(pre, max)
      }
      return max
    }
    console.log(maxSubArray([-1,5,-3,7,3,4,6,-5,6]));
  </script>
</body>

</html>